// 格雷编码

package Leetcode;

import java.util.ArrayList;
import java.util.List;

class solution_089 {
    public List<Integer> grayCode(int n) {
        // 存储2^n种结果
        List<String> result = new ArrayList<>();
        // 2^n种排列顺序
        String[] binaryString = new String[(int) Math.pow(2, n)];
        for (int i = 0; i < Math.pow(2, n); i++) {
            binaryString[i] = Integer.toBinaryString(i);
            if (binaryString[i].length() < n) {
                for (int j = binaryString[i].length(); j < n; j++)
                    binaryString[i] = '0' + binaryString[i];
            }
        }
        // for (String s : binaryString)
        // System.out.println(s);
        // 确定是否被访问过
        boolean[] isVisited = new boolean[(int) Math.pow(2, n)];
        DFS(result, binaryString, isVisited, n);

        List<Integer> ans = new ArrayList<>();
        for (String s : result)
            ans.add(Integer.valueOf(s, 2));
        return ans;
    }

    public void DFS(List<String> result, String[] binaryString, boolean[] isVisited, int n) {
        // 数量达到则停止
        if (result.size() >= Math.pow(2, n))
            return;
        // result为空添加0
        else if (result.size() == 0) {
            result.add(new String(binaryString[0]));
            isVisited[0] = true;
            DFS(result, binaryString, isVisited, n);
            isVisited[0] = false;
        } else {
            char[] lastString = result.get(result.size() - 1).toCharArray();
            for (int i = n - 1; i >= 0; i--) {
                // 取某一位以及它的相反值
                char c1 = lastString[i];
                char c = c1 == '0' ? '1' : '0';
                lastString[i] = c;
                // 此时的下标
                int index = Integer.valueOf(String.valueOf(lastString), 2);
                // 如果该数字没有被访问
                if (isVisited[index] == false) {
                    result.add(new String(binaryString[index]));
                    isVisited[index] = true;
                    DFS(result, binaryString, isVisited, n);
                    isVisited[index] = false;
                    break;
                } else {
                    lastString[i] = c1;
                }
            } // for
        } // else
    } // DFS

    public static void main(String[] args) {
        // solution_089 s = new solution_089();
        // int x = 3;
        // s.grayCode(x);
        // System.out.println(Integer.toBinaryString(x));
        System.out.println(1 << 1);
        System.out.println(1 << 2);
        System.out.println(1 << 3);
    }
}

public class Solution089 {
    // 使用归纳法
    // public List<Integer> grayCode(int n) {
    // List<Integer> result = new ArrayList<>();
    // result.add(0);
    // for (int i = 1; i <= n; i++) {
    // int size = result.size();
    // for (int j = size - 1; j >= 0; j--)
    // result.add(result.get(j) | 1 << (i - 1));
    // }
    // return result;
    // }

    // 使用公式法
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < 1 << n; i++) {
            result.add(i ^ (i / 2));
        }
        return result;
    }
}
